#include <iostream>
using namespace std;
#define INF INT_MAX

const int n = 10; //一共有10个单词
const int M = 8;  //每行最多容纳8个字符

//一种实用功能打印解决方案
int print_line(int p[], int j, char *str[])
{
    int k, i = p[j];
    cout << i << " " << j <<endl;    
    if (i == 1)
        k = 1;
    else
        k = print_line(p, i - 1, str) + 1;

    cout << "Line number:" << k << " ";
    for (int t = i; t <= j; t++)
    {
        cout << str[t - 1] << " ";
    }
    cout << endl;
    return k;
}

// l[]表示不同单词的输入序列的长度。例如，
// l[] = {3, 2, 2, 5} 对于像 "aaa bb cc ddddd"一句.  n 是大小尺寸。
// l[] M 是一行宽度 (没有最大字符串能填满一行)
void pprint(int l[], char *str[])
{
    //为简单起见，extra数组空间用于存放每行剩余空格数
    //如果从单词i到单词j可以放在一行，那么spaceLeft[i][j]表示剩余空格数
    int **spaceLeft, i, j;
    spaceLeft = new int *[n + 1];
    for (i = 0; i <= n; i++)
    {
        spaceLeft[i] = new int[n + 1];
    }
    //sc[i][j]表示从单词i到单词j的一行的代价(空格数的立方)
    int **sc;
    sc = new int *[n + 1];
    for (i = 0; i <= n; i++)
    {
        sc[i] = new int[n + 1];
    }
    //c[i]表示从单词i到单词j最优代价和(空格数最小立方和)
    int *c = new int[n + 1];

    // p[] 用于打印解决方案
    int *p = new int[n + 1];

    //计算每行的剩余空格数。
    //若单词i到单词j可以放到一行，那么extra[i][j]值意味着是此行的剩余空格数。
    for (i = 1; i <= n; i++)
    {
        spaceLeft[i][i] = M - l[i - 1]; //
        for (j = i + 1; j <= n; j++)
        {
            spaceLeft[i][j] = spaceLeft[i][j - 1] - l[j - 1] - 1;
        }
    }
    //用上述剩余空格数(数组extra)来计算行代价(数组sc)。
    //若单词i到单词j可以放到一行，sc[i][j]值表示此行的代价。
    for (i = 1; i <= n; i++)
    {
        for (j = i; j <= n; j++)
        {
            if (spaceLeft[i][j] < 0)
                sc[i][j] = INF;
            else if (j == n && spaceLeft[i][j] >= 0)
                sc[i][j] = 0;
            else
                sc[i][j] = spaceLeft[i][j] * spaceLeft[i][j] * spaceLeft[i][j];
        }
    }

    //计算最小代价并且找到最小代价的每行换行处。
    //c[j]意味着从单词1到单词j的最优总代价(代价=立方和)
    c[0] = 0;
    for (j = 1; j <= n; j++)
    {
        c[j] = INF;
        for (i = 1; i <= j; i++)
        {
            if (c[i - 1] != INF && sc[i][j] != INF && (c[i - 1] + sc[i][j] < c[j]))
            {
                c[j] = c[i - 1] + sc[i][j];
                p[j] = i;
            }
        }
        cout << c[j] << " " << j << " " << p[j] <<endl;
    }


    print_line(p, n, str);
    delete []c;
    delete []p;
    for (i = 0; i <= n; i++)
    {
        delete sc[i];
    }
    for (i = 0; i <= n; i++)
    {
        delete spaceLeft[i];
    }
}

//主程序测试上述功能
int main()
{
    char *str[n] = {"abc", "def", "gh", "polq", "cs", "opaqe", "klfgh", "t", "asd", "th"};
    int l[n];
    for (int i = 0; i < n; i++)
    {
        l[i] = strlen(str[i]);
    }
    pprint(l, str);
    return 0;
}
